home *** CD-ROM | disk | FTP | other *** search
/ Openstep 4.2 (Developer) / Openstep Developer 4.2.iso / NextDeveloper / Source / GNU / perl / Perl / ext / SDBM_File / sdbm / sdbm.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-02  |  10.7 KB  |  521 lines
  1. /*
  2.  * sdbm - ndbm work-alike hashed database library
  3.  * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
  4.  * author: oz@nexus.yorku.ca
  5.  * status: public domain.
  6.  *
  7.  * core routines
  8.  */
  9.  
  10. #ifndef lint
  11. static char rcsid[] = "$Id: sdbm.c,v 1.16 90/12/13 13:01:31 oz Exp $";
  12. #endif
  13.  
  14. #include "config.h"
  15. #include "sdbm.h"
  16. #include "tune.h"
  17. #include "pair.h"
  18.  
  19. #ifdef I_FCNTL
  20. # include <fcntl.h>
  21. #endif
  22. #ifdef I_SYS_FILE
  23. # include <sys/file.h>
  24. #endif
  25.  
  26. #ifdef I_STRING
  27. # include <string.h>
  28. #else
  29. # include <strings.h>
  30. #endif
  31.  
  32. /*
  33.  * externals
  34.  */
  35. #ifndef sun
  36. extern int errno;
  37. #endif
  38.  
  39. extern Malloc_t malloc proto((MEM_SIZE));
  40. extern Free_t free proto((void *));
  41. extern Off_t lseek();
  42.  
  43. /*
  44.  * forward
  45.  */
  46. static int getdbit proto((DBM *, long));
  47. static int setdbit proto((DBM *, long));
  48. static int getpage proto((DBM *, long));
  49. static datum getnext proto((DBM *));
  50. static int makroom proto((DBM *, long, int));
  51.  
  52. /*
  53.  * useful macros
  54.  */
  55. #define bad(x)        ((x).dptr == NULL || (x).dsize < 0)
  56. #define exhash(item)    sdbm_hash((item).dptr, (item).dsize)
  57. #define ioerr(db)    ((db)->flags |= DBM_IOERR)
  58.  
  59. #define OFF_PAG(off)    (long) (off) * PBLKSIZ
  60. #define OFF_DIR(off)    (long) (off) * DBLKSIZ
  61.  
  62. static long masks[] = {
  63.     000000000000, 000000000001, 000000000003, 000000000007,
  64.     000000000017, 000000000037, 000000000077, 000000000177,
  65.     000000000377, 000000000777, 000000001777, 000000003777,
  66.     000000007777, 000000017777, 000000037777, 000000077777,
  67.     000000177777, 000000377777, 000000777777, 000001777777,
  68.     000003777777, 000007777777, 000017777777, 000037777777,
  69.     000077777777, 000177777777, 000377777777, 000777777777,
  70.     001777777777, 003777777777, 007777777777, 017777777777
  71. };
  72.  
  73. datum nullitem = {NULL, 0};
  74.  
  75. DBM *
  76. sdbm_open(file, flags, mode)
  77. register char *file;
  78. register int flags;
  79. register int mode;
  80. {
  81.     register DBM *db;
  82.     register char *dirname;
  83.     register char *pagname;
  84.     register int n;
  85.  
  86.     if (file == NULL || !*file)
  87.         return errno = EINVAL, (DBM *) NULL;
  88. /*
  89.  * need space for two seperate filenames
  90.  */
  91.     n = strlen(file) * 2 + strlen(DIRFEXT) + strlen(PAGFEXT) + 2;
  92.  
  93.     if ((dirname = malloc((unsigned) n)) == NULL)
  94.         return errno = ENOMEM, (DBM *) NULL;
  95. /*
  96.  * build the file names
  97.  */
  98.     dirname = strcat(strcpy(dirname, file), DIRFEXT);
  99.     pagname = strcpy(dirname + strlen(dirname) + 1, file);
  100.     pagname = strcat(pagname, PAGFEXT);
  101.  
  102.     db = sdbm_prep(dirname, pagname, flags, mode);
  103.     free((char *) dirname);
  104.     return db;
  105. }
  106.  
  107. DBM *
  108. sdbm_prep(dirname, pagname, flags, mode)
  109. char *dirname;
  110. char *pagname;
  111. int flags;
  112. int mode;
  113. {
  114.     register DBM *db;
  115.     struct stat dstat;
  116.  
  117.     if ((db = (DBM *) malloc(sizeof(DBM))) == NULL)
  118.         return errno = ENOMEM, (DBM *) NULL;
  119.  
  120.         db->flags = 0;
  121.         db->hmask = 0;
  122.         db->blkptr = 0;
  123.         db->keyptr = 0;
  124. /*
  125.  * adjust user flags so that WRONLY becomes RDWR, 
  126.  * as required by this package. Also set our internal
  127.  * flag for RDONLY if needed.
  128.  */
  129.     if (flags & O_WRONLY)
  130.         flags = (flags & ~O_WRONLY) | O_RDWR;
  131.  
  132.     else if ((flags & 03) == O_RDONLY)
  133.         db->flags = DBM_RDONLY;
  134. /*
  135.  * open the files in sequence, and stat the dirfile.
  136.  * If we fail anywhere, undo everything, return NULL.
  137.  */
  138.     if ((db->pagf = open(pagname, flags, mode)) > -1) {
  139.         if ((db->dirf = open(dirname, flags, mode)) > -1) {
  140. /*
  141.  * need the dirfile size to establish max bit number.
  142.  */
  143.             if (fstat(db->dirf, &dstat) == 0) {
  144. /*
  145.  * zero size: either a fresh database, or one with a single,
  146.  * unsplit data page: dirpage is all zeros.
  147.  */
  148.                 db->dirbno = (!dstat.st_size) ? 0 : -1;
  149.                 db->pagbno = -1;
  150.                 db->maxbno = dstat.st_size * BYTESIZ;
  151.  
  152.                 (void) memset(db->pagbuf, 0, PBLKSIZ);
  153.                 (void) memset(db->dirbuf, 0, DBLKSIZ);
  154.             /*
  155.              * success
  156.              */
  157.                 return db;
  158.             }
  159.             (void) close(db->dirf);
  160.         }
  161.         (void) close(db->pagf);
  162.     }
  163.     free((char *) db);
  164.     return (DBM *) NULL;
  165. }
  166.  
  167. void
  168. sdbm_close(db)
  169. register DBM *db;
  170. {
  171.     if (db == NULL)
  172.         errno = EINVAL;
  173.     else {
  174.         (void) close(db->dirf);
  175.         (void) close(db->pagf);
  176.         free((char *) db);
  177.     }
  178. }
  179.  
  180. datum
  181. sdbm_fetch(db, key)
  182. register DBM *db;
  183. datum key;
  184. {
  185.     if (db == NULL || bad(key))
  186.         return errno = EINVAL, nullitem;
  187.  
  188.     if (getpage(db, exhash(key)))
  189.         return getpair(db->pagbuf, key);
  190.  
  191.     return ioerr(db), nullitem;
  192. }
  193.  
  194. int
  195. sdbm_delete(db, key)
  196. register DBM *db;
  197. datum key;
  198. {
  199.     if (db == NULL || bad(key))
  200.         return errno = EINVAL, -1;
  201.     if (sdbm_rdonly(db))
  202.         return errno = EPERM, -1;
  203.  
  204.     if (getpage(db, exhash(key))) {
  205.         if (!delpair(db->pagbuf, key))
  206.             return -1;
  207. /*
  208.  * update the page file
  209.  */
  210.         if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
  211.             || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
  212.             return ioerr(db), -1;
  213.  
  214.         return 0;
  215.     }
  216.  
  217.     return ioerr(db), -1;
  218. }
  219.  
  220. int
  221. sdbm_store(db, key, val, flags)
  222. register DBM *db;
  223. datum key;
  224. datum val;
  225. int flags;
  226. {
  227.     int need;
  228.     register long hash;
  229.  
  230.     if (db == NULL || bad(key))
  231.         return errno = EINVAL, -1;
  232.     if (sdbm_rdonly(db))
  233.         return errno = EPERM, -1;
  234.  
  235.     need = key.dsize + val.dsize;
  236. /*
  237.  * is the pair too big (or too small) for this database ??
  238.  */
  239.     if (need < 0 || need > PAIRMAX)
  240.         return errno = EINVAL, -1;
  241.  
  242.     if (getpage(db, (hash = exhash(key)))) {
  243. /*
  244.  * if we need to replace, delete the key/data pair
  245.  * first. If it is not there, ignore.
  246.  */
  247.         if (flags == DBM_REPLACE)
  248.             (void) delpair(db->pagbuf, key);
  249. #ifdef SEEDUPS
  250.         else if (duppair(db->pagbuf, key))
  251.             return 1;
  252. #endif
  253. /*
  254.  * if we do not have enough room, we have to split.
  255.  */
  256.         if (!fitpair(db->pagbuf, need))
  257.             if (!makroom(db, hash, need))
  258.                 return ioerr(db), -1;
  259. /*
  260.  * we have enough room or split is successful. insert the key,
  261.  * and update the page file.
  262.  */
  263.         (void) putpair(db->pagbuf, key, val);
  264.  
  265.         if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
  266.             || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
  267.             return ioerr(db), -1;
  268.     /*
  269.      * success
  270.      */
  271.         return 0;
  272.     }
  273.  
  274.     return ioerr(db), -1;
  275. }
  276.  
  277. /*
  278.  * makroom - make room by splitting the overfull page
  279.  * this routine will attempt to make room for SPLTMAX times before
  280.  * giving up.
  281.  */
  282. static int
  283. makroom(db, hash, need)
  284. register DBM *db;
  285. long hash;
  286. int need;
  287. {
  288.     long newp;
  289.     char twin[PBLKSIZ];
  290.     char *pag = db->pagbuf;
  291.     char *new = twin;
  292.     register int smax = SPLTMAX;
  293.  
  294.     do {
  295. /*
  296.  * split the current page
  297.  */
  298.         (void) splpage(pag, new, db->hmask + 1);
  299. /*
  300.  * address of the new page
  301.  */
  302.         newp = (hash & db->hmask) | (db->hmask + 1);
  303.  
  304. /*
  305.  * write delay, read avoidence/cache shuffle:
  306.  * select the page for incoming pair: if key is to go to the new page,
  307.  * write out the previous one, and copy the new one over, thus making
  308.  * it the current page. If not, simply write the new page, and we are
  309.  * still looking at the page of interest. current page is not updated
  310.  * here, as sdbm_store will do so, after it inserts the incoming pair.
  311.  */
  312.         if (hash & (db->hmask + 1)) {
  313.             if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
  314.                 || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
  315.                 return 0;
  316.             db->pagbno = newp;
  317.             (void) memcpy(pag, new, PBLKSIZ);
  318.         }
  319.         else if (lseek(db->pagf, OFF_PAG(newp), SEEK_SET) < 0
  320.              || write(db->pagf, new, PBLKSIZ) < 0)
  321.             return 0;
  322.  
  323.         if (!setdbit(db, db->curbit))
  324.             return 0;
  325. /*
  326.  * see if we have enough room now
  327.  */
  328.         if (fitpair(pag, need))
  329.             return 1;
  330. /*
  331.  * try again... update curbit and hmask as getpage would have
  332.  * done. because of our update of the current page, we do not
  333.  * need to read in anything. BUT we have to write the current
  334.  * [deferred] page out, as the window of failure is too great.
  335.  */
  336.         db->curbit = 2 * db->curbit +
  337.             ((hash & (db->hmask + 1)) ? 2 : 1);
  338.         db->hmask |= db->hmask + 1;
  339.  
  340.         if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
  341.             || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
  342.             return 0;
  343.  
  344.     } while (--smax);
  345. /*
  346.  * if we are here, this is real bad news. After SPLTMAX splits,
  347.  * we still cannot fit the key. say goodnight.
  348.  */
  349. #ifdef BADMESS
  350.     (void) write(2, "sdbm: cannot insert after SPLTMAX attempts.\n", 44);
  351. #endif
  352.     return 0;
  353.  
  354. }
  355.  
  356. /*
  357.  * the following two routines will break if
  358.  * deletions aren't taken into account. (ndbm bug)
  359.  */
  360. datum
  361. sdbm_firstkey(db)
  362. register DBM *db;
  363. {
  364.     if (db == NULL)
  365.         return errno = EINVAL, nullitem;
  366. /*
  367.  * start at page 0
  368.  */
  369.     if (lseek(db->pagf, OFF_PAG(0), SEEK_SET) < 0
  370.         || read(db->pagf, db->pagbuf, PBLKSIZ) < 0)
  371.         return ioerr(db), nullitem;
  372.     db->pagbno = 0;
  373.     db->blkptr = 0;
  374.     db->keyptr = 0;
  375.  
  376.     return getnext(db);
  377. }
  378.  
  379. datum
  380. sdbm_nextkey(db)
  381. register DBM *db;
  382. {
  383.     if (db == NULL)
  384.         return errno = EINVAL, nullitem;
  385.     return getnext(db);
  386. }
  387.  
  388. /*
  389.  * all important binary trie traversal
  390.  */
  391. static int
  392. getpage(db, hash)
  393. register DBM *db;
  394. register long hash;
  395. {
  396.     register int hbit;
  397.     register long dbit;
  398.     register long pagb;
  399.  
  400.     dbit = 0;
  401.     hbit = 0;
  402.     while (dbit < db->maxbno && getdbit(db, dbit))
  403.         dbit = 2 * dbit + ((hash & (1 << hbit++)) ? 2 : 1);
  404.  
  405.     debug(("dbit: %d...", dbit));
  406.  
  407.     db->curbit = dbit;
  408.     db->hmask = masks[hbit];
  409.  
  410.     pagb = hash & db->hmask;
  411. /*
  412.  * see if the block we need is already in memory.
  413.  * note: this lookaside cache has about 10% hit rate.
  414.  */
  415.     if (pagb != db->pagbno) { 
  416. /*
  417.  * note: here, we assume a "hole" is read as 0s.
  418.  * if not, must zero pagbuf first.
  419.  */
  420.         if (lseek(db->pagf, OFF_PAG(pagb), SEEK_SET) < 0
  421.             || read(db->pagf, db->pagbuf, PBLKSIZ) < 0)
  422.             return 0;
  423.         if (!chkpage(db->pagbuf))
  424.             return 0;
  425.         db->pagbno = pagb;
  426.  
  427.         debug(("pag read: %d\n", pagb));
  428.     }
  429.     return 1;
  430. }
  431.  
  432. static int
  433. getdbit(db, dbit)
  434. register DBM *db;
  435. register long dbit;
  436. {
  437.     register long c;
  438.     register long dirb;
  439.  
  440.     c = dbit / BYTESIZ;
  441.     dirb = c / DBLKSIZ;
  442.  
  443.     if (dirb != db->dirbno) {
  444.         if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0
  445.             || read(db->dirf, db->dirbuf, DBLKSIZ) < 0)
  446.             return 0;
  447.         db->dirbno = dirb;
  448.  
  449.         debug(("dir read: %d\n", dirb));
  450.     }
  451.  
  452.     return db->dirbuf[c % DBLKSIZ] & (1 << dbit % BYTESIZ);
  453. }
  454.  
  455. static int
  456. setdbit(db, dbit)
  457. register DBM *db;
  458. register long dbit;
  459. {
  460.     register long c;
  461.     register long dirb;
  462.  
  463.     c = dbit / BYTESIZ;
  464.     dirb = c / DBLKSIZ;
  465.  
  466.     if (dirb != db->dirbno) {
  467.         if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0
  468.             || read(db->dirf, db->dirbuf, DBLKSIZ) < 0)
  469.             return 0;
  470.         db->dirbno = dirb;
  471.  
  472.         debug(("dir read: %d\n", dirb));
  473.     }
  474.  
  475.     db->dirbuf[c % DBLKSIZ] |= (1 << dbit % BYTESIZ);
  476.  
  477.     if (dbit >= db->maxbno)
  478.         db->maxbno += DBLKSIZ * BYTESIZ;
  479.  
  480.     if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0
  481.         || write(db->dirf, db->dirbuf, DBLKSIZ) < 0)
  482.         return 0;
  483.  
  484.     return 1;
  485. }
  486.  
  487. /*
  488.  * getnext - get the next key in the page, and if done with
  489.  * the page, try the next page in sequence
  490.  */
  491. static datum
  492. getnext(db)
  493. register DBM *db;
  494. {
  495.     datum key;
  496.  
  497.     for (;;) {
  498.         db->keyptr++;
  499.         key = getnkey(db->pagbuf, db->keyptr);
  500.         if (key.dptr != NULL)
  501.             return key;
  502. /*
  503.  * we either run out, or there is nothing on this page..
  504.  * try the next one... If we lost our position on the
  505.  * file, we will have to seek.
  506.  */
  507.         db->keyptr = 0;
  508.         if (db->pagbno != db->blkptr++)
  509.             if (lseek(db->pagf, OFF_PAG(db->blkptr), SEEK_SET) < 0)
  510.                 break;
  511.         db->pagbno = db->blkptr;
  512.         if (read(db->pagf, db->pagbuf, PBLKSIZ) <= 0)
  513.             break;
  514.         if (!chkpage(db->pagbuf))
  515.             break;
  516.     }
  517.  
  518.     return ioerr(db), nullitem;
  519. }
  520.  
  521.